package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最长递增子序列的个数
 *
 * 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
 * 注意 这个数列必须是 严格 递增的。
 *
 * author: Mr.Du
 * Date: 2023/11/1
 * Time: 17:09
 */
public class FindNumberOfLIS {

    public int findNumberOfLIS(int[] nums) {
        int m = nums.length;
        // dp[i] 表示以i结尾的最长递增子序列
        int[] dp = new int[m];
        // count[i] 表示以i结尾的最长递增子序列的个数
        int[] count = new int[m];
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        int max = dp[0];
        for(int i = 1;i < m;i++){
            for(int j = 0;j < i;j++){
                if(nums[i] > nums[j]){
                    if(dp[i] == dp[j] + 1){
                        count[i] += count[j];
                    }else if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }
                }
                if (dp[i] > max) max = dp[i];
            }
        }
        int res = 0;
        for(int i = 0; i < m; i++){
            if(max == dp[i]) res += count[i];
        }
        return res;

    }

    public static void main(String[] args) {
        FindNumberOfLIS findNumberOfLIS = new FindNumberOfLIS();
        int[] nums = {1,2,4,3,5,4,7,2};
        findNumberOfLIS.findNumberOfLIS(nums);
    }
}
